//
//  234. 回文链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/9.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

// 判定一个链表是否是回文链表
// 找到中间节点
// 反转后半部分节点
class Solution234 {
    // 是否是回文链表
    func isPalindrome(_ head: ListNode?) -> Bool {
        let mid = finMid(head)
        let head2 = reverseList(mid)
        
        var p1 = head
        var p2 = head2
        while p2 != nil  {
            if p1?.val == p2?.val {
                p1 = p1?.next
                p2 = p2?.next
            } else {
                return false
            }
        }
        return true
    }
    func finMid(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
    func reverseList(_ node: ListNode?) -> ListNode? {
        var pre: ListNode?
        var cur = node
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
        return pre
    }
    static func test(){
        let root: ListNode? = createNode()
        let solution = Solution234()
        let result = solution.isPalindrome(root)
        print(result)
    }
    static func createNode() -> ListNode{
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(2)
        let node4 = ListNode(1)
    
        node1.next = node2
        node2.next = node3
        node3.next = node4
        
        return node1
    }
    
}
